home *** CD-ROM | disk | FTP | other *** search
/ AmigActive 23 / AACD 23.iso / AACD / Programming / Wipeout / source / allocator.c < prev    next >
C/C++ Source or Header  |  2001-02-06  |  14KB  |  618 lines
  1. /*
  2.  * $Id: allocator.c 1.14 1998/04/16 11:03:41 olsen Exp olsen $
  3.  *
  4.  * :ts=4
  5.  *
  6.  * Wipeout -- Traces and munges memory and detects memory trashing
  7.  *
  8.  * Written by Olaf `Olsen' Barthel <olsen@sourcery.han.de>
  9.  * Public Domain
  10.  */
  11.  
  12. #ifndef _GLOBAL_H
  13. #include "global.h"
  14. #endif    /* _GLOBAL_H */
  15.  
  16. /******************************************************************************/
  17.  
  18. #include "installpatches.h"
  19.  
  20. /******************************************************************************/
  21.  
  22. STATIC struct MinList AllocationList;
  23.  
  24. /******************************************************************************/
  25.  
  26. STATIC VOID
  27. AddAllocation(struct TrackHeader * th)
  28. {
  29.     /* Register the new regular memory allocation. */
  30.     AddTail((struct List *)&AllocationList,(struct Node *)th);
  31. }
  32.  
  33. STATIC VOID
  34. RemoveAllocation(struct TrackHeader * th)
  35. {
  36.     /* Unregister the regular memory allocation. */
  37.     Remove((struct Node *)th);
  38.     th->th_Magic = 0;
  39. }
  40.  
  41. /******************************************************************************/
  42.  
  43. ULONG
  44. CalculateChecksum(const ULONG * mem,ULONG memSize)
  45. {
  46.     ULONG tmp,sum;
  47.     int i;
  48.  
  49.     /* memSize must be a multiple of 4. */
  50.     ASSERT((memSize % 4) == 0);
  51.  
  52.     /* Calculate the "additive carry wraparound" checksum
  53.      * for the given memory area. The Kickstart and the boot block
  54.      * checksums are calculated using the same technique.
  55.      */
  56.     sum = 0;
  57.     for(i = 0 ; i < memSize / 4 ; i++)
  58.     {
  59.         tmp = sum + mem[i];
  60.         if(tmp < sum)
  61.             tmp++;
  62.  
  63.         sum = tmp;
  64.     }
  65.  
  66.     return(sum);
  67. }
  68.  
  69. /******************************************************************************/
  70.  
  71. VOID
  72. FixTrackHeaderChecksum(struct TrackHeader * th)
  73. {
  74.     ASSERT(th != NULL);
  75.  
  76.     /* Protect everything but the MinNode at the beginning
  77.      * with a checksum.
  78.      */
  79.     th->th_Checksum = 0;
  80.     th->th_Checksum = ~CalculateChecksum((ULONG *)&th->th_PoolHeader,
  81.                                          sizeof(*th) - offsetof(struct TrackHeader,th_PoolHeader));
  82. }
  83.  
  84. /******************************************************************************/
  85.  
  86. VOID
  87. PerformDeallocation(struct TrackHeader * th)
  88. {
  89.     BOOL mungMem = FALSE;
  90.     LONG allocationSize;
  91.     APTR poolHeader;
  92.  
  93.     allocationSize = th->th_NameTagLen + sizeof(*th) + PreWallSize + th->th_Size + th->th_PostSize;
  94.  
  95.     /* It is quasi-legal to release and reuse memory whilst under
  96.      * Forbid(). If this is the case, we will not stomp on the allocation
  97.      * body and leave the contents of the buffer unmodified. Note that
  98.      * while in Disable() state, multitasking will be halted, just as whilst
  99.      * in Forbid() state. But as there is no safe way to track whether the
  100.      * system actually has the interrupts disabled and because the memory
  101.      * allocator is documented to operate under Forbid() conditions only,
  102.      * we just consider the Forbid() state.
  103.      */
  104.     if(NoReuse || SysBase->TDNestCnt == 0) /* not -1 because we always run under Forbid() */
  105.         mungMem = TRUE;
  106.  
  107.     switch(th->th_Type)
  108.     {
  109.         case ALLOCATIONTYPE_AllocMem:
  110.         case ALLOCATIONTYPE_AllocVec:
  111.  
  112.             RemoveAllocation(th);
  113.  
  114.             /* skip the name tag header, if there is one */
  115.             if(th->th_NameTagLen > 0)
  116.                 th = (struct TrackHeader *)(((ULONG)th) - th->th_NameTagLen);
  117.  
  118.             /* munge the entire allocation, not just the allocation body. */
  119.             if(mungMem)
  120.                 MungMem((ULONG *)th,allocationSize,DEADBEEF);
  121.  
  122.             (*OldFreeMem)(th,allocationSize,SysBase);
  123.             break;
  124.  
  125.         case ALLOCATIONTYPE_AllocPooled:
  126.  
  127.             RemovePuddle(th);
  128.  
  129.             /* remember this, as it may be gone in a minute */
  130.             poolHeader = th->th_PoolHeader->ph_PoolHeader;
  131.  
  132.             /* skip the name tag header, if there is one */
  133.             if(th->th_NameTagLen > 0)
  134.                 th = (struct TrackHeader *)(((ULONG)th) - th->th_NameTagLen);
  135.  
  136.             /* munge the entire allocation, not just the allocation body. */
  137.             if(mungMem)
  138.                 MungMem((ULONG *)th,allocationSize,DEADBEEF);
  139.  
  140.             (*OldFreePooled)(poolHeader,th,allocationSize,SysBase);
  141.             break;
  142.     }
  143. }
  144.  
  145. /******************************************************************************/
  146.  
  147. BOOL
  148. PerformAllocation(
  149.     ULONG                    pc,
  150.     struct PoolHeader *        poolHeader,
  151.     ULONG                    memSize,
  152.     ULONG                    attributes,
  153.     UBYTE                    type,
  154.     APTR *                    resultPtr)
  155. {
  156.     struct TrackHeader * th;
  157.     ULONG preSize;
  158.     ULONG allocationRemainder;
  159.     ULONG postSize;
  160.     LONG nameTagLen;
  161.     APTR result = NULL;
  162.     BOOL success = FALSE;
  163.  
  164.     nameTagLen = 0;
  165.  
  166.     /* Get the name of the current task, if this is necessary. */
  167.     if(NameTag)
  168.         nameTagLen = GetNameTagLen(pc);
  169.  
  170.     /* If the allocation is not a multiple of the memory granularity
  171.      * block size, increase the post memory wall by the remaining
  172.      * few bytes of padding.
  173.      */
  174.     allocationRemainder = (memSize % MEM_BLOCKSIZE);
  175.     if(allocationRemainder > 0)
  176.         allocationRemainder = MEM_BLOCKSIZE - allocationRemainder;
  177.  
  178.     preSize = PreWallSize;
  179.     postSize = allocationRemainder + PostWallSize;
  180.  
  181.     switch(type)
  182.     {
  183.         case ALLOCATIONTYPE_AllocMem:
  184.  
  185.             th = (*OldAllocMem)(nameTagLen + sizeof(*th) + preSize + memSize + postSize,attributes & (~MEMF_CLEAR),SysBase);
  186.             if(th != NULL)
  187.             {
  188.                 /* Store the name tag data in front of the header, then
  189.                  * adjust the header address.
  190.                  */
  191.                 if(nameTagLen > 0)
  192.                 {
  193.                     FillNameTag(th,nameTagLen);
  194.                     th = (struct TrackHeader *)(((ULONG)th) + nameTagLen);
  195.                 }
  196.  
  197.                 AddAllocation(th);
  198.             }
  199.  
  200.             break;
  201.  
  202.         case ALLOCATIONTYPE_AllocVec:
  203.  
  204.             /* This will later contain the length long word. */
  205.             memSize += sizeof(ULONG);
  206.  
  207.             th = (*OldAllocMem)(nameTagLen + sizeof(*th) + preSize + memSize + postSize,attributes & (~MEMF_CLEAR),SysBase);
  208.             if(th != NULL)
  209.             {
  210.                 /* Store the name tag data in front of the header, then
  211.                  * adjust the header address.
  212.                  */
  213.                 if(nameTagLen > 0)
  214.                 {
  215.                     FillNameTag(th,nameTagLen);
  216.                     th = (struct TrackHeader *)(((ULONG)th) + nameTagLen);
  217.                 }
  218.  
  219.                 AddAllocation(th);
  220.             }
  221.  
  222.             break;
  223.  
  224.         case ALLOCATIONTYPE_AllocPooled:
  225.  
  226.             th = (*OldAllocPooled)(poolHeader->ph_PoolHeader,nameTagLen + sizeof(*th) + preSize + memSize + postSize,SysBase);
  227.             if(th != NULL)
  228.             {
  229.                 /* Store the name tag data in front of the header, then
  230.                  * adjust the header address.
  231.                  */
  232.                 if(nameTagLen > 0)
  233.                 {
  234.                     FillNameTag(th,nameTagLen);
  235.                     th = (struct TrackHeader *)(((ULONG)th) + nameTagLen);
  236.                 }
  237.  
  238.                 AddPuddle(poolHeader,th);
  239.             }
  240.  
  241.             break;
  242.  
  243.         default:
  244.  
  245.             th = NULL;
  246.             break;
  247.     }
  248.  
  249.     if(th != NULL)
  250.     {
  251.         STATIC ULONG Sequence;
  252.  
  253.         UBYTE * mem;
  254.  
  255.         /* Fill in the regular header data. */
  256.         th->th_Magic        = BASEBALL;
  257.         th->th_PointBack    = th;
  258.         th->th_PC            = pc;
  259.         th->th_Owner        = FindTask(NULL);
  260.         th->th_OwnerType    = GetTaskType(NULL);
  261.         th->th_NameTagLen    = nameTagLen;
  262.  
  263.         GetSysTime(&th->th_Time);
  264.         th->th_Sequence = Sequence++;
  265.  
  266.         th->th_Size            = memSize;
  267.         th->th_PoolHeader    = poolHeader;
  268.         th->th_Type            = type;
  269.         th->th_FillChar        = NewFillChar();
  270.         th->th_PostSize        = postSize;
  271.         th->th_Marked        = FALSE;
  272.  
  273.         /* Calculate the checksum. */
  274.         FixTrackHeaderChecksum(th);
  275.  
  276.         /* Fill in the preceding memory wall. */
  277.         mem = (UBYTE *)(th + 1);
  278.  
  279.         memset(mem,th->th_FillChar,preSize);
  280.         mem += preSize;
  281.  
  282.         /* Fill the memory allocation body either with
  283.          * junk or with zeroes.
  284.          */
  285.         if(FLAG_IS_CLEAR(attributes,MEMF_CLEAR))
  286.             MungMem((ULONG *)mem,memSize,DEADFOOD);
  287.         else
  288.             memset(mem,0,memSize);
  289.  
  290.         mem += memSize;
  291.  
  292.         /* Fill in the following memory wall. */
  293.         memset(mem,th->th_FillChar,postSize);
  294.  
  295.         mem = (UBYTE *)(th + 1);
  296.         mem += preSize;
  297.  
  298.         /* AllocVec()'ed allocations are special in that
  299.          * the size of the allocation precedes the header.
  300.          */
  301.         if(type == ALLOCATIONTYPE_AllocVec)
  302.         {
  303.             /* Size of the allocation must include the
  304.              * size long word.
  305.              */
  306.             (*(ULONG *)mem) = memSize + sizeof(ULONG);
  307.  
  308.             result = (APTR)(mem + sizeof(ULONG));
  309.         }
  310.         else
  311.         {
  312.             result = (APTR)mem;
  313.         }
  314.  
  315.         success = TRUE;
  316.     }
  317.  
  318.     (*resultPtr) = result;
  319.  
  320.     return(success);
  321. }
  322.  
  323. /******************************************************************************/
  324.  
  325. BOOL
  326. IsValidTrackHeader(struct TrackHeader * th)
  327. {
  328.     BOOL valid = FALSE;
  329.  
  330.     /* Check whether the calculated address looks good enough. */
  331.     if(NOT IsInvalidAddress((ULONG)th) && NOT IsOddAddress((ULONG)th))
  332.     {
  333.         /* Check for the unique identifiers. */
  334.         if(th->th_Magic == BASEBALL && th->th_PointBack == th)
  335.             valid = TRUE;
  336.     }
  337.  
  338.     return(valid);
  339. }
  340.  
  341. /******************************************************************************/
  342.  
  343. BOOL
  344. IsTrackHeaderChecksumCorrect(struct TrackHeader * th)
  345. {
  346.     BOOL isCorrect = FALSE;
  347.  
  348.     /* For extra safety, also take a look at the checksum. */
  349.     if(CalculateChecksum((ULONG *)&th->th_PoolHeader,
  350.                          sizeof(*th) - offsetof(struct TrackHeader,th_PoolHeader)) == (ULONG)-1)
  351.     {
  352.         isCorrect = TRUE;
  353.     }
  354.  
  355.     return(isCorrect);
  356. }
  357.  
  358. /******************************************************************************/
  359.  
  360. BOOL
  361. IsTrackedAllocation(
  362.     ULONG                    address,
  363.     struct TrackHeader **    resultPtr)
  364. {
  365.     struct TrackHeader * result = NULL;
  366.     struct TrackHeader * th;
  367.     BOOL valid = FALSE;
  368.  
  369.     /* Move back to the memory tracking header. */
  370.     th = (struct TrackHeader *)(address - PreWallSize - sizeof(*th));
  371.  
  372.     /* Check if the track header is valid. */
  373.     if(IsValidTrackHeader(th) && IsTrackHeaderChecksumCorrect(th))
  374.     {
  375.         result = th;
  376.         valid = TRUE;
  377.     }
  378.  
  379.     (*resultPtr) = result;
  380.  
  381.     return(valid);
  382. }
  383.  
  384. /******************************************************************************/
  385.  
  386. VOID
  387. SetupAllocationList(VOID)
  388. {
  389.     /* Initialize the list of regular memory allocations.
  390.      * Pooled allocations will be stored elsewhere.
  391.      */
  392.     NewList((struct List *)&AllocationList);
  393. }
  394.  
  395. /******************************************************************************/
  396.  
  397. VOID
  398. CheckAllocatedMemory(VOID)
  399. {
  400.     ULONG totalBytes;
  401.     ULONG totalAllocations;
  402.  
  403.     /* Check and count all regular memory allocations. We look for
  404.      * trashed memory walls and orphaned memory.
  405.      */
  406.  
  407.     totalBytes = 0;
  408.     totalAllocations = 0;
  409.  
  410.     Forbid();
  411.  
  412.     if(IsAllocationListConsistent())
  413.     {
  414.         struct TrackHeader * th;
  415.  
  416.         for(th = (struct TrackHeader *)AllocationList.mlh_Head ;
  417.             th->th_MinNode.mln_Succ != NULL ;
  418.             th = (struct TrackHeader *)th->th_MinNode.mln_Succ)
  419.         {
  420.             /* A magic value of 0 indicates a "dead" allocation
  421.              * that we left to its own devices. We don't want it
  422.              * to show up in our list.
  423.              */
  424.             if(th->th_Magic != 0)
  425.             {
  426.                 /* Check for trashed memory walls. */
  427.                 CheckStomping(NULL,th);
  428.  
  429.                 /* Check if its creator is still with us. */
  430.                 if(NOT IsTaskStillAround(th->th_Owner))
  431.                     VoiceComplaint(NULL,th,"Orphaned allocation?\n");
  432.  
  433.                 totalBytes += th->th_Size;
  434.                 totalAllocations++;
  435.             }
  436.         }
  437.     }
  438.  
  439.     Permit();
  440.  
  441.     DPrintf("%ld byte(s) in %ld single allocation(s).\n",totalBytes,totalAllocations);
  442. }
  443.  
  444. /******************************************************************************/
  445.  
  446. VOID
  447. ShowUnmarkedMemory(VOID)
  448. {
  449.     ULONG totalBytes;
  450.     ULONG totalAllocations;
  451.  
  452.     /* Show and count all unmarked regular memory allocations. */
  453.  
  454.     totalBytes = 0;
  455.     totalAllocations = 0;
  456.  
  457.     Forbid();
  458.  
  459.     if(IsAllocationListConsistent())
  460.     {
  461.         struct TrackHeader * th;
  462.  
  463.         for(th = (struct TrackHeader *)AllocationList.mlh_Head ;
  464.             th->th_MinNode.mln_Succ != NULL ;
  465.             th = (struct TrackHeader *)th->th_MinNode.mln_Succ)
  466.         {
  467.             /* A magic value of 0 indicates a "dead" allocation
  468.              * that we left to its own devices. We don't want it
  469.              * to show up in our list.
  470.              */
  471.             if(th->th_Magic != 0)
  472.             {
  473.                 if(NOT th->th_Marked)
  474.                     VoiceComplaint(NULL,th,NULL);
  475.  
  476.                 totalBytes += th->th_Size;
  477.                 totalAllocations++;
  478.             }
  479.         }
  480.     }
  481.  
  482.     Permit();
  483.  
  484.     DPrintf("%ld byte(s) in %ld single allocation(s).\n",totalBytes,totalAllocations);
  485. }
  486.  
  487. /******************************************************************************/
  488.  
  489. VOID
  490. ChangeMemoryMarks(BOOL markSet)
  491. {
  492.     /* Mark or unmark all memory puddles. */
  493.  
  494.     Forbid();
  495.  
  496.     if(IsAllocationListConsistent())
  497.     {
  498.         struct TrackHeader * th;
  499.  
  500.         for(th = (struct TrackHeader *)AllocationList.mlh_Head ;
  501.             th->th_MinNode.mln_Succ != NULL ;
  502.             th = (struct TrackHeader *)th->th_MinNode.mln_Succ)
  503.         {
  504.             /* A magic value of 0 indicates a "dead" allocation
  505.              * that we left to its own devices.
  506.              */
  507.             if(th->th_Magic != 0)
  508.             {
  509.                 th->th_Marked = markSet;
  510.  
  511.                 /* Repair the checksum value. */
  512.                 FixTrackHeaderChecksum(th);
  513.             }
  514.         }
  515.     }
  516.  
  517.     Permit();
  518. }
  519.  
  520. /******************************************************************************/
  521.  
  522. BOOL
  523. IsAllocationListConsistent(VOID)
  524. {
  525.     BOOL isConsistent = TRUE;
  526.  
  527.     Forbid();
  528.  
  529.     if(NOT IsMemoryListConsistent(&AllocationList))
  530.     {
  531.         isConsistent = FALSE;
  532.  
  533.         DPrintf("\a** TRACKED MEMORY LIST INCONSISTENT!!! **\n");
  534.  
  535.         NewList((struct List *)&AllocationList);
  536.     }
  537.  
  538.     Permit();
  539.  
  540.     return(isConsistent);
  541. }
  542.  
  543. /******************************************************************************/
  544.  
  545. BOOL
  546. IsMemoryListConsistent(struct MinList * mlh)
  547. {
  548.     BOOL isConsistent = TRUE;
  549.  
  550.     if(CheckConsistency)
  551.     {
  552.         struct TrackHeader * th;
  553.         struct timeval lastTime = {0,0};
  554.         ULONG lastSequence = 0;
  555.         BOOL haveData = FALSE;
  556.  
  557.         for(th = (struct TrackHeader *)mlh->mlh_Head ;
  558.             th->th_MinNode.mln_Succ != NULL ;
  559.             th = (struct TrackHeader *)th->th_MinNode.mln_Succ)
  560.         {
  561.             /* check whether the header data is consistent */
  562.             if(NOT IsInvalidAddress((ULONG)th) &&
  563.                NOT IsOddAddress((ULONG)th) &&
  564.                IsTrackHeaderChecksumCorrect(th))
  565.             {
  566.                 /* do not test dead allocations */
  567.                 if(th->th_Magic != 0)
  568.                 {
  569.                     /* check for the unique identifiers */
  570.                     if(th->th_Magic == BASEBALL && th->th_PointBack == th)
  571.                     {
  572.                         /* the following is to check whether there are
  573.                          * cycles in the allocation list which may have
  574.                          * resulted through strange and unlikely memory
  575.                          * trashing
  576.                          */
  577.                         if(haveData)
  578.                         {
  579.                             LONG result = (-CmpTime(&th->th_Time,&lastTime));
  580.  
  581.                             if(result == 0) /* both allocation times are the same? */
  582.                             {
  583.                                 /* allocation sequence is smaller than previous? */
  584.                                 if(th->th_Sequence <= lastSequence)
  585.                                 {
  586.                                     isConsistent = FALSE;
  587.                                     break;
  588.                                 }
  589.                             }
  590.                             else if (result < 0) /* allocation is older than previous? */
  591.                             {
  592.                                 isConsistent = FALSE;
  593.                             }
  594.                         }
  595.  
  596.                         lastTime        = th->th_Time;
  597.                         lastSequence    = th->th_Sequence;
  598.  
  599.                         haveData = TRUE;
  600.                     }
  601.                     else
  602.                     {
  603.                         isConsistent = FALSE;
  604.                         break;
  605.                     }
  606.                 }
  607.             }
  608.             else
  609.             {
  610.                 isConsistent = FALSE;
  611.                 break;
  612.             }
  613.         }
  614.     }
  615.  
  616.     return(isConsistent);
  617. }
  618.